package leetcode;

/**
 * Created by Ghost on 2014/12/9 0009.
 */
public class Search_for_a_Range {
    public int[] searchRange(int[] A, int target) {
        int start = -1,end = -1;
        int[] rst = new int[2];
        rst[0] = start;
        rst[1] = end;

        if(A==null)
            return rst;
        int left = 0, right = A.length-1;
        while(left<=right){
            int mid = (left+right)>>1;
            if(A[mid]==target){
                int i;
                for(i=mid;i>=0 && A[i]==target;i--);
                start = i+1;
                for(i=mid;i<A.length && A[i]==target;i++);
                end = i-1;
                break;
            } else if(A[mid]<target){
                left = mid+1;
            }
            else
                right = mid-1;
        }
        rst[0] = start;
        rst[1] = end;
        return rst;
    }

    public static void main(String[] args){
        Search_for_a_Range search_for_a_range = new Search_for_a_Range();
        int[] A = {6};
        int[] rst = search_for_a_range.searchRange(A,6);
        System.out.println(rst[0]+"  "+rst[1]);
    }
}
